class Solution {
    int ret = 0;
    boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(n, 1);
        return ret;
    }
    public void dfs(int n, int pos){
        if(pos > n){
            ret++;
            return;
        }
        for(int i = 1; i <= n; i++){
            // 剪枝
            if(!check[i] && judge(i, pos)){
                check[i] = true;
                dfs(n, pos + 1);
                // 回溯
                check[i] = false;
            }
        }
    }
    private boolean judge(int n, int pos){
        if(n % pos == 0 || pos % n == 0) return true;
        return false;
    }
}